插入排序

就是将一个数据插入到已经有序的数据中，从而得到一个新的、个数加一的有序数据，适用于少量数据的排序。

插入排序的工作过程

基本思想：每步将一个待排序的记录，按排序要求插入到前面已经排序的数据中适当位置上，直到全部插入完为止。

代码实现

def insert_sort(alist):
    """插入排序"""

    # 列表长度
    n = len(alist)

    # 控制轮数
    for j in range(1, n):
        # 找到合适的位置安放我们的无序的数据
        for i in range(j, 0, -1): # [j, j - 1, j - 2, ...., 1]
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
            else:
                break
if __name__ == '__main__':
    alist = [1, 100, 99, 20, 5, 1000]
    insert_sort(alist)
    print(alist)

插入排序的稳定性

最差时间复杂度$O(n^2)$，最优时间复杂度O(n)。插入排序是一种稳定算法。